from typing import List


class Solution:
    """
    方法： 使用动态规划判断数组是否可以分割成两个和相等的子集
           dp[j]表示是否可以从数组中选择若干个数使其和为j
           对于每个数x，从大到小更新dp[j]:
           dp[j] = dp[j] or dp[j-x]
           如果dp[s]为真，说明可以找到和为s的子集，则可以分割
    
    Args:
        nums: List[int] - 输入的整数数组
    
    Returns:
        bool: 数组是否可以分割成两个和相等的子集
    
    Time: O(n*s) - n为数组长度，s为数组和的一半
    
    Space: O(s) - 需要一个长度为s的数组存储动态规划状态
    """
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2:
            return False
        s = total // 2
        dp = [True] + [False] * s
        s2 = 0
        for i,x in enumerate(nums):
            s2 = min(s2 + x, s)
            for j in range(s2, x - 1, -1):
                dp[j] = dp[j] or dp[j-x]
            if dp[s]:
                return True
        return False